﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

public class Solution15
{
    public IList<IList<int>> ThreeSum(int[] nums)
    {
        Array.Sort(nums);//排序
        IList<IList<int>> res = new List<IList<int>>();

        for (int i = 0; i < nums.Length - 2; i++)
        {
            if (i > 0 && nums[i] == nums[i - 1])
            {
                //跳过
            }
            else
            {
                int left = i + 1;
            int right = nums.Length - 1;

                while (left < right)
                {
                    if (nums[i] + nums[left] + nums[right] > 0)//缩小
                    {
                        right--;
                    }
                    else if (nums[i] + nums[left] + nums[right] < 0)//放大
                    {
                        left++;

                    }
                    else
                    {//收集答案
                        //Console.WriteLine("res");
                        IList<int> cur = new List<int>
                    {
                        nums[i],
                        nums[left],
                        nums[right]
                    };
                        res.Add(cur);

                        //把重复的都跳过去
                        while (left + 1 < nums.Length - 1&& nums[left+1]== nums[left ])
                        {
                            Console.WriteLine(nums[left]);
                            left++;
                        }
                        while (right - 1>i&&nums[right - 1] == nums[right])
                        {
                            Console.WriteLine(nums[right]);
                            right--;
                        }
                        left++;
                        right--;


                    }
                }

            }



        }
        return res;

    }
    //先写一个三重循环的版本，超时
    public IList<IList<int>> ThreeSum2(int[] nums)
    {
        Array.Sort(nums);//排序
        IList<IList<int>> res = new List<IList<int>>();

        for (int first = 0; first < nums.Length - 2; first++)
        {
            if (first > 0 && nums[first] == nums[first - 1])
            {
                //跳过
            }
            else
            {
                for (int second = first + 1; second < nums.Length - 1; second++)
                {
                    //second可以和first一样，但是不可以和前一个second一样

                    if (second - 1 != first && nums[second] == nums[second - 1])
                    {
                        //跳过
                    }
                    else
                    {
                        for (int third = second + 1; third < nums.Length; third++)
                        {

                            if (third - 1 != second && nums[third] == nums[third - 1])
                            {
                                //跳过
                            }
                            else
                            {
                                if (nums[third] + nums[second] + nums[first] == 0)
                                {
                                    //收集
                                    IList<int> cur = new List<int>
                    {
                        nums[third],
                        nums[first],
                        nums[second]
                    };
                                    res.Add(cur);
                                }

                            }

                        }

                    }



                }
            }


        }
        return res;

    }
}

class Program15
{
    static void Main15(string[] args)
    {
        Solution15 solution = new Solution15();

        int[] nums = [-1, 0, 1, 2, -1, -4];
        IList<IList<int>> res = solution.ThreeSum(nums);
        for (int i = 0; i < res.Count; i++)
        {
            for (int j = 0; j < res[i].Count; j++)
            {


                Console.Write(res[i][j] + ",");
            }
            Console.WriteLine();
        }
    }
}
